package Hot100.Medium.GreedyAndDP.DynamicPlanning.CompleteBag;

public class LC279_NumSquares {
    public static void main(String[] args) {

    }

    public int numSquares(int n){
        int max = Integer.MAX_VALUE / 2;
        int m = (int)Math.sqrt(n);
        // 确定dp数组含义dp[i][j]表示用前i个完全平方数能够组成的背包容量为j的最少组合数量
        int[][] dp = new int[m + 1][n + 1];
        // 初始化dp数组
        // 第一列dp[i][0]，由于题目说了n>=1，因此毫无疑问为0
        for(int i = 0; i <= m; i++){
            dp[i][0] = 0;
        }
        // 第一行，对于背包容量为j时，第一行完全平方数为0，由于不能用0组成，或者可以理解为无限种，因此设置max
        for(int j = 0; j <= n; j++){
            dp[0][j] = max;
        }

        // 确定递推公式，完全背包通用公式dp[i][j] = MATH.max(dp[i - 1][j], dp[i][j-weight[i]] + value[i])
        // 对于本题考虑通式变体，由于填入dp的是有几种组成办法，且要求最少数量，因此用min
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++) {
                if(Math.pow(i,2) > j){// j容量放不下
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][(int) (j - Math.pow(i,2))] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
